home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1994 November: Tool Chest / Dev.CD Nov 94.toast / Tool Chest / Development Tools & Languages / • Other Platforms / PCCTS / support / rexpr / rexpr.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-09-14  |  10.3 KB  |  527 lines  |  [TEXT/MPS ]
  1. /*
  2.  * This file contains code for
  3.  *
  4.  *      int rexpr(char *expr, char *s);
  5.  *
  6.  * which answers
  7.  *
  8.  *      1 if 's' is in the language described by the regular expression 'expr'
  9.  *      0 if it is not
  10.  *     -1 if the regular expression is invalid
  11.  *
  12.  * Language membership is determined by constructing a non-deterministic
  13.  * finite automata (NFA) from the regular expression.  A depth-
  14.  * first-search is performed on the NFA (graph) to check for a match of 's'.
  15.  * Each non-epsilon arc consumes one character from 's'.  Backtracking is
  16.  * performed to check all possible paths through the NFA.
  17.  *
  18.  * Regular expressions follow the meta-language:
  19.  *
  20.  * <regExpr>        ::= <andExpr> ( '|' <andExpr> )*
  21.  *
  22.  * <andExpr>        ::= <expr> ( <expr> )*
  23.  *
  24.  * <expr>           ::= {'~'} '[' <atomList> ']' <repeatSymbol>
  25.  *                      | '(' <regExpr> ')' <repeatSymbol>
  26.  *                      | '{' <regExpr> '}' <repeatSymbol>
  27.  *                      | <atom> <repeatSymbol>
  28.  *
  29.  * <repeatSymbol>   ::= { '*' | '+' }
  30.  *
  31.  * <atomList>       ::= <atom> ( <atom> )*
  32.  *                      | { <atomList> } <atom> '-' <atom> { <atomList> }
  33.  *
  34.  * <atom>           ::= Token[Atom]
  35.  *
  36.  * Notes:
  37.  *        ~    means complement the set in [..]. i.e. all characters not listed
  38.  *        *    means match 0 or more times (can be on expression or atom)
  39.  *        +    means match 1 or more times (can be on expression or atom)
  40.  *        {}    optional
  41.  *        ()    grouping
  42.  *        []    set of atoms
  43.  *        x-y    all characters from x to y (found only in [..])
  44.  *        \xx the character with value xx
  45.  *
  46.  * Examples:
  47.  *        [a-z]+
  48.  *            match 1 or more lower-case letters (e.g. variable)
  49.  *
  50.  *        0x[0-9A-Fa-f]+
  51.  *            match a hex number with 0x on front (e.g. 0xA1FF)
  52.  *
  53.  *        [0-9]+.[0-9]+{e[0-9]+}
  54.  *            match a floating point number (e.g. 3.14e21)
  55.  *
  56.  * Code example:
  57.  *        if ( rexpr("[a-zA-Z][a-zA-Z0-9]+", str) ) then str is keyword
  58.  *
  59.  * Terence Parr
  60.  * Purdue University
  61.  * April 1991
  62.  */
  63.  
  64. #include <stdio.h>
  65. #include <ctype.h>
  66. #ifdef __STDC__
  67. #include <stdlib.h>
  68. #else
  69. #include <malloc.h>
  70. #endif
  71. #include "rexpr.h"
  72.  
  73. #ifdef __STDC__
  74. static int regExpr( GraphPtr g );
  75. static int andExpr( GraphPtr g );
  76. static int expr( GraphPtr g );
  77. static int repeatSymbol( GraphPtr g );
  78. static int atomList( char *p, int complement );
  79. static int next( void );
  80. static ArcPtr newGraphArc( void );
  81. static NodePtr newNode( void );
  82. static int ArcBetweenGraphNode( NodePtr i, NodePtr j, int label );
  83. static Graph BuildNFA_atom( int label );
  84. static Graph BuildNFA_AB( Graph A, Graph B );
  85. static Graph BuildNFA_AorB( Graph A, Graph B );
  86. static Graph BuildNFA_set( char *s );
  87. static Graph BuildNFA_Astar( Graph A );
  88. static Graph BuildNFA_Aplus( Graph A );
  89. static Graph BuildNFA_Aoptional( Graph A );
  90. #else
  91. static int regExpr();
  92. static int andExpr();
  93. static int expr();
  94. static int repeatSymbol();
  95. static int atomList();
  96. static int next();
  97. static ArcPtr newGraphArc();
  98. static NodePtr newNode();
  99. static int ArcBetweenGraphNode();
  100. static Graph BuildNFA_atom();
  101. static Graph BuildNFA_AB();
  102. static Graph BuildNFA_AorB();
  103. static Graph BuildNFA_set();
  104. static Graph BuildNFA_Astar();
  105. static Graph BuildNFA_Aplus();
  106. static Graph BuildNFA_Aoptional();
  107. #endif
  108.  
  109. static char *_c;
  110. static int token, tokchar;
  111. static NodePtr accept;
  112. static NodePtr freelist = NULL;
  113.  
  114. /*
  115.  * return 1 if s in language described by expr
  116.  *        0 if s is not
  117.  *       -1 if expr is an invalid regular expression
  118.  */
  119. rexpr(expr, s)
  120. char *expr, *s;
  121. {
  122.     NodePtr p,q;
  123.     Graph nfa;
  124.     int result;
  125.  
  126.     fprintf(stderr, "rexpr(%s,%s);\n", expr,s);
  127.     freelist = NULL;
  128.     _c = expr;
  129.     next();
  130.     if ( regExpr(&nfa) == -1 ) return -1;
  131.     accept = nfa.right;
  132.     result = match(nfa.left, s);
  133.     /* free all your memory */
  134.     p = q = freelist;
  135.     while ( p!=NULL ) { q = p->track; free(p); p = q; }
  136.     return result;
  137. }
  138.  
  139. /*
  140.  * do a depth-first-search on the NFA looking for a path from start to
  141.  * accept state labelled with the characters of 's'.
  142.  */
  143. match(automaton, s)
  144. NodePtr automaton;
  145. char *s;
  146. {
  147.     ArcPtr p;
  148.     
  149.     if ( automaton == accept && *s == '\0' ) return 1;    /* match */
  150.  
  151.     for (p=automaton->arcs; p!=NULL; p=p->next)            /* try all arcs */
  152.     {
  153.         if ( p->label == Epsilon )
  154.         {
  155.             if ( match(p->target, s) ) return 1;
  156.         }
  157.         else if ( p->label == *s )
  158.                 if ( match(p->target, s+1) ) return 1;
  159.     }
  160.     return 0;
  161. }
  162.  
  163. /*
  164.  * <regExpr>        ::= <andExpr> ( '|' {<andExpr>} )*
  165.  *
  166.  * Return -1 if syntax error
  167.  * Return  0 if none found
  168.  * Return  1 if a regExrp was found
  169.  */
  170. static
  171. regExpr(g)
  172. GraphPtr g;
  173. {
  174.     Graph g1, g2;
  175.     
  176.     if ( andExpr(&g1) == -1 )
  177.     {
  178.         return -1;
  179.     }
  180.     
  181.     while ( token == '|' )
  182.     {
  183.         int a;
  184.         next();
  185.         a = andExpr(&g2);
  186.         if ( a == -1 ) return -1;    /* syntax error below */
  187.         else if ( !a ) return 1;    /* empty alternative */
  188.         g1 = BuildNFA_AorB(g1, g2);
  189.     }
  190.     
  191.     if ( token!='\0' ) return -1;
  192.  
  193.     *g = g1;
  194.     return 1;
  195. }
  196.  
  197. /*
  198.  * <andExpr>        ::= <expr> ( <expr> )*
  199.  */
  200. static
  201. andExpr(g)
  202. GraphPtr g;
  203. {
  204.     Graph g1, g2;
  205.     
  206.     if ( expr(&g1) == -1 )
  207.     {
  208.         return -1;
  209.     }
  210.     
  211.     while ( token==Atom || token=='{' || token=='(' || token=='~' || token=='[' )
  212.     {
  213.         if (expr(&g2) == -1) return -1;
  214.         g1 = BuildNFA_AB(g1, g2);
  215.     }
  216.     
  217.     *g = g1;
  218.     return 1;
  219. }
  220.  
  221. /*
  222.  * <expr>           ::=    {'~'} '[' <atomList> ']' <repeatSymbol>
  223.  *                      | '(' <regExpr> ')' <repeatSymbol>
  224.  *                      | '{' <regExpr> '}' <repeatSymbol>
  225.  *                      | <atom> <repeatSymbol>
  226.  */
  227. static
  228. expr(g)
  229. GraphPtr g;
  230. {
  231.     int complement = 0;
  232.     char s[257];    /* alloc space for string of char in [] */
  233.     
  234.     if ( token == '~' || token == '[' )
  235.     {
  236.         if ( token == '~' ) {complement = 1; next();}
  237.         if ( token != '[' ) return -1;
  238.         next();
  239.         if ( atomList( s, complement ) == -1 ) return -1;
  240.         *g = BuildNFA_set( s );
  241.         if ( token != ']' ) return -1;
  242.         next();
  243.         repeatSymbol( g );
  244.         return 1;
  245.     }
  246.     if ( token == '(' )
  247.     {
  248.         next();
  249.         if ( regExpr( g ) == -1 ) return -1;
  250.         if ( token != ')' ) return -1;
  251.         next();
  252.         repeatSymbol( g );
  253.         return 1;
  254.     }
  255.     if ( token == '{' )
  256.     {
  257.         next();
  258.         if ( regExpr( g ) == -1 ) return -1;
  259.         if ( token != '}' ) return -1;
  260.         next();
  261.         /* S p e c i a l  C a s e   O p t i o n a l  {  } */
  262.         if ( token != '*' && token != '+' )
  263.         {
  264.             *g = BuildNFA_Aoptional( *g );
  265.         }
  266.         repeatSymbol( g );
  267.         return 1;
  268.     }
  269.     if ( token == Atom )
  270.     {
  271.         *g = BuildNFA_atom( tokchar );
  272.         next();
  273.         repeatSymbol( g );
  274.         return 1;
  275.     }
  276.     
  277.     return -1;
  278. }
  279.  
  280. /*
  281.  * <repeatSymbol>   ::= { '*' | '+' }
  282.  */
  283. static
  284. repeatSymbol(g)
  285. GraphPtr g;
  286. {
  287.     switch ( token )
  288.     {
  289.         case '*' : *g = BuildNFA_Astar( *g ); next(); break;
  290.         case '+' : *g = BuildNFA_Aplus( *g ); next(); break;
  291.     }
  292.     return 1;
  293. }
  294.  
  295. /*
  296.  * <atomList>       ::= <atom> { <atom> }*
  297.  *                      { <atomList> } <atom> '-' <atom> { <atomList> }
  298.  *
  299.  * a-b is same as ab
  300.  * q-a is same as q
  301.  */
  302. static
  303. atomList(p, complement)
  304. char *p;
  305. int complement;
  306. {
  307.     static unsigned char set[256];        /* no duplicates */
  308.     int first, last, i;
  309.     char *s = p;
  310.     
  311.     if ( token != Atom ) return -1;
  312.     
  313.     for (i=0; i<256; i++) set[i] = 0;
  314.     while ( token == Atom )
  315.     {
  316.         if ( !set[tokchar] ) *s++ = tokchar;
  317.         set[tokchar] = 1;                /* Add atom to set */
  318.         next();
  319.         if ( token == '-' )             /* have we found '-' */
  320.         {
  321.             first = *(s-1);             /* Get last char */
  322.             next();
  323.             if ( token != Atom ) return -1;
  324.             else
  325.             {
  326.                 last = tokchar;
  327.             }
  328.             for (i = first+1; i <= last; i++)
  329.             {
  330.                 if ( !set[tokchar] ) *s++ = i;
  331.                 set[i] = 1;                /* Add atom to set */
  332.             }
  333.             next();
  334.         }
  335.     }
  336.     *s = '\0';
  337.     if ( complement )
  338.     {
  339.         for (i=0; i<256; i++) set[i] = !set[i];
  340.         for (i=1,s=p; i<256; i++) if ( set[i] ) *s++ = i;
  341.         *s = '\0';
  342.     }
  343.     return 1;
  344. }
  345.  
  346. /* a somewhat stupid lexical analyzer */
  347. static
  348. next()
  349. {
  350.     while ( *_c==' ' || *_c=='\t' || *_c=='\n' ) _c++;
  351.     if ( *_c=='\\' )
  352.     {
  353.         _c++;
  354.         if ( isdigit(*_c) )
  355.         {
  356.             int n=0;
  357.             while ( isdigit(*_c) )
  358.             {
  359.                 n = n*10 + (*_c++ - '0');
  360.             }
  361.             if ( n>255 ) n=255;
  362.             tokchar = n;
  363.         }
  364.         else
  365.         {
  366.             switch (*_c)
  367.             {
  368.                 case 'n' : tokchar = '\n'; break;
  369.                 case 't' : tokchar = '\t'; break;
  370.                 case 'r' : tokchar = '\r'; break;
  371.                 default  : tokchar = *_c;
  372.             }
  373.             _c++;
  374.         }
  375.         token = Atom;
  376.     }
  377.     else if ( isgraph(*_c) && *_c!='[' && *_c!='(' && *_c!='{' &&
  378.               *_c!='-' && *_c!='}' && *_c!=')' && *_c!=']' &&
  379.               *_c!='+' && *_c!='*' && *_c!='~' && *_c!='|' )
  380.     {
  381.         token = Atom;
  382.         tokchar = *_c++;
  383.     }
  384.     else
  385.     {
  386.         token = tokchar = *_c++;
  387.     }
  388. }
  389.  
  390. /* N F A  B u i l d i n g  R o u t i n e s */
  391.  
  392. static
  393. ArcPtr
  394. newGraphArc()
  395. {
  396.     ArcPtr p;
  397.     p = (ArcPtr) calloc(1, sizeof(Arc));
  398.     if ( p==NULL ) {fprintf(stderr,"rexpr: out of memory\n"); exit(-1);}
  399.     if ( freelist != NULL ) p->track = (ArcPtr) freelist;
  400.     freelist = (NodePtr) p;
  401.     return p;
  402. }
  403.  
  404. static
  405. NodePtr
  406. newNode()
  407. {
  408.     NodePtr p;
  409.     p = (NodePtr) calloc(1, sizeof(Node));
  410.     if ( p==NULL ) {fprintf(stderr,"rexpr: out of memory\n"); exit(-1);}
  411.     if ( freelist != NULL ) p->track = freelist;
  412.     freelist = p;
  413.     return p;
  414. }
  415.  
  416. static
  417. ArcBetweenGraphNodes(i, j, label)
  418. NodePtr i, j;
  419. int label;
  420. {
  421.     ArcPtr a;
  422.     
  423.     a = newGraphArc();
  424.     if ( i->arcs == NULL ) i->arctail = i->arcs = a;
  425.     else {(i->arctail)->next = a; i->arctail = a;}
  426.     a->label = label;
  427.     a->target = j;
  428. }
  429.  
  430. static Graph
  431. BuildNFA_atom(label)
  432. int label;
  433. {
  434.     Graph g;
  435.     
  436.     g.left = newNode();
  437.     g.right = newNode();
  438.     ArcBetweenGraphNodes(g.left, g.right, label);
  439.     return( g );
  440. }
  441.  
  442. static Graph
  443. BuildNFA_AB(A, B)
  444. Graph A, B;
  445. {
  446.     Graph g;
  447.     
  448.     ArcBetweenGraphNodes(A.right, B.left, Epsilon);
  449.     g.left = A.left;
  450.     g.right = B.right;
  451.     return( g );
  452. }
  453.  
  454. static Graph
  455. BuildNFA_AorB(A, B)
  456. Graph A, B;
  457. {
  458.     Graph g;
  459.     
  460.     g.left = newNode();
  461.     ArcBetweenGraphNodes(g.left, A.left, Epsilon);
  462.     ArcBetweenGraphNodes(g.left, B.left, Epsilon);
  463.     g.right = newNode();
  464.     ArcBetweenGraphNodes(A.right, g.right, Epsilon);
  465.     ArcBetweenGraphNodes(B.right, g.right, Epsilon);
  466.     return( g );
  467. }
  468.  
  469. static Graph
  470. BuildNFA_set( s )
  471. char *s;
  472. {
  473.     Graph g;
  474.     
  475.     if ( s == NULL ) return g;
  476.     
  477.     g.left = newNode();
  478.     g.right = newNode();
  479.     while ( *s != '\0' )
  480.     {
  481.         ArcBetweenGraphNodes(g.left, g.right, *s++);
  482.     }
  483.     return g;
  484. }
  485.  
  486. static Graph
  487. BuildNFA_Astar( A )
  488. Graph A;
  489. {
  490.     Graph g;
  491.  
  492.     g.left = newNode();
  493.     g.right = newNode();
  494.     
  495.     ArcBetweenGraphNodes(g.left, A.left, Epsilon);
  496.     ArcBetweenGraphNodes(g.left, g.right, Epsilon);
  497.     ArcBetweenGraphNodes(A.right, g.right, Epsilon);
  498.     ArcBetweenGraphNodes(A.right, A.left, Epsilon);
  499.     
  500.     return( g );
  501. }
  502.  
  503. static Graph
  504. BuildNFA_Aplus( A )
  505. Graph A;
  506. {
  507.     ArcBetweenGraphNodes(A.right, A.left, Epsilon);
  508.     
  509.     return( A );
  510. }
  511.  
  512. static Graph
  513. BuildNFA_Aoptional( A )
  514. Graph A;
  515. {
  516.     Graph g;
  517.     
  518.     g.left = newNode();
  519.     g.right = newNode();
  520.     
  521.     ArcBetweenGraphNodes(g.left, A.left, Epsilon);
  522.     ArcBetweenGraphNodes(g.left, g.right, Epsilon);
  523.     ArcBetweenGraphNodes(A.right, g.right, Epsilon);
  524.     
  525.     return( g );
  526. }
  527.